package ink.lvxin.datastructure.ch4tree;

import ink.lvxin.datastructure.utils.StringUtils;

import javax.xml.crypto.Data;

/**
 * 二叉查找树
 * @author LvXin
 */
public class BinarySearchTree<T extends Comparable<? super T>> {
    /**
     * 二叉树节点
     * @author LvXin
     */
    private static class BinaryNode<T> {
        public BinaryNode(T data) {
            this(data, null, null);
        }

        public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        T data;

        BinaryNode<T> left;
        BinaryNode<T> right;
    }

    private BinaryNode<T> root;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(BinaryNode<T> root) {
        this.root = root;
    }

    public void makeEmpty() {
        this.root = null;
    }

    public boolean isEmpty() {
        return this.root == null;
    }

    public boolean contains(T t) {
        return contains(t, root);
    }

    public void insert(T t) {
        this.root = insert(t, root);
    }

    private BinaryNode<T> insert(T t, BinaryNode<T> node) {
        if (node == null) {
            return new BinaryNode<>(t);
        }

        int compareResult = t.compareTo(node.data);
        if (compareResult < 0) {
            node.left = insert(t, node.left);
        } else if (compareResult > 0) {
            node.right = insert(t, node.right);
        } else {
            ;
        }

        return node;
    }

    private boolean contains(T t, BinaryNode<T> root) {
        if (t == null || root == null) {
            return false;
        }

        int compareResult = t.compareTo(root.data);

        if (compareResult < 0) {
            return contains(t, root.left);
        } else if (compareResult > 0) {
            return contains(t, root.right);
        } else {
            return true;
        }

    }

    public void print() {
        print(root,new StringBuilder());
    }

    private void print(BinaryNode<T> node,StringBuilder indent) {
        if (node == null) {
            return;
        }

        String lineStr = "|____";
        String indentStr = StringUtils.getSpaceStrByLength(lineStr.length());

        System.out.println(node.data);
        if (node.left == null && node.right == null) {
            return;
        }

        StringBuilder indentNext = new StringBuilder();
        indentNext.append(indent).append(indentStr);
        if (node.left != null) {
            System.out.print(indent.toString() + lineStr);
            print(node.left,indentNext);
        }
        if (node.right != null) {
            System.out.print(indent.toString() + lineStr);
            print(node.right,indentNext);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(5);
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(6);
        tree.insert(7);
        tree.insert(8);
        tree.insert(9);

        tree.print();
    }

}
